void test() {
  ll mod = 1000000007;
  sieve();
  assert_equal(0ll, M(0));
  assert_equal(1ll, M(1));
  assert_equal(-87856LL, M(100000000000));
  assert_equal(999999858LL-mod, M(746128406));
  assert_equal(6947LL, M(1277022208));
  assert_equal(999999250LL-mod, M(115107799));
  assert_equal(999994324LL-mod, M(698764825));
  assert_equal(999997726LL-mod, M(477765955));
  assert_equal(999999591LL-mod, M(13281242));
  assert_equal(1210LL, M(55017566));
  assert_equal(1705LL, M(792470199));
  assert_equal(999996523LL-mod, M(282986454));
  assert_equal(4212LL, M(218911984));
  assert_equal(999993750LL-mod, M(661076163));
  assert_equal(7433LL, M(938020851));
  assert_equal(8259LL, M(947179460));
  assert_equal(999997037LL-mod, M(183596626));
  assert_equal(1861LL, M(1354596138));
  assert_equal(999997538LL-mod, M(278779260));
  assert_equal(1922LL, M(589967458));
  assert_equal(999997045LL-mod, M(683991345));
  assert_equal(999997207LL-mod, M(722860638));
  assert_equal(999998589LL-mod, M(263488964));
  assert_equal(999997639LL-mod, M(75572056));
  assert_equal(8053LL, M(1247287103));
  assert_equal(999993613LL-mod, M(665271448));
  assert_equal(999999388LL-mod, M(19383773));
  assert_equal(150LL, M(739407443));
  assert_equal(2246LL, M(506866615));
  assert_equal(303LL, M(202000780));
  assert_equal(999996575LL-mod, M(638579340));
  assert_equal(892LL, M(852274015));
  assert_equal(5164LL, M(568507197));
  assert_equal(999996491LL-mod, M(728126511));
  assert_equal(4756LL, M(1308875868));
  assert_equal(6378LL, M(1319812371));
  assert_equal(999998856LL-mod, M(829560621));
  assert_equal(5029LL, M(1302848612));
  assert_equal(1448LL, M(137282862));
  assert_equal(484LL, M(66768409));
  assert_equal(999999945LL-mod, M(127858832));
  assert_equal(2853LL, M(509610331));
  assert_equal(3431LL, M(1430789126));
}
// vim: cc=60 ts=2 sts=2 sw=2:
